contents

자바 백엔드 개발자로서 검색에 사용되는 트리 데이터 구조(이진 탐색 트리, B-트리, 레드-블랙 트리, B+ 트리 등)에 대한 이해는 매우 중요합니다. 아래에 각 구조의 정의, 구조, 특성, 연산, 활용 사례를 상세히 설명합니다.

1. 이진 탐색 트리 (BST: Binary Search Tree)

정의 및 구조

• 이진 탐색 트리는 각 노드가 키를 하나씩 가지고 있으며, 기준 노드의 왼쪽 자식에는 더 작은 값, 오른쪽 자식에는 더 큰 값이 저장됩니다.
• 각 노드는 최대 두 개의 자식(왼쪽, 오른쪽)을 가집니다.

주요 연산

• 탐색(Search): 루트(최상위 노드)부터 시작해서 크기 비교로 왼쪽/오른쪽으로 이동합니다.
• 삽입/삭제: 탐색 경로를 따라 이동하며 노드를 추가/제거합니다.

시간 복잡도

• 평균/최선: O(log n)
• 최악(트리가 한쪽으로 치우친 경우): O(n)

2. B-트리

정의 및 구조

• B-트리는 자기 균형을 유지하며, 각 노드가 둘 이상의 자식(최대 m개까지)을 가질 수 있는 다중 탐색 트리입니다. 주로 데이터베이스나 파일 시스템에 사용됩니다.
• 각 노드는 여러 개의 키와 자식 포인터를 가지며, 내부 노드는 경로 안내, 리프 노드는 실제 데이터를 저장합니다.

특성

• 루트를 제외한 모든 노드는 최소 m/2 ~ 최대 m개의 자식.
• 모든 키는 정렬된 상태.
• 모든 리프 노드가 동일한 깊이에 존재.
• 노드 분할/병합으로 균형 유지.

주요 연산

• 탐색: 여러 키와 비교하며 자식 경로로 진행.
• 삽입/삭제: 노드 분할/병합 과정을 통해 균형 유지.

3. B+ 트리

정의 및 구조

• B+ 트리는 B-트리의 변형으로, 데이터 포인터는 리프(최종) 노드에만 저장되며 내부 노드는 경로 안내 역할을 합니다.
• 리프 노드들이 서로 연결되어 있어 빠른 범위 탐색이 가능.

특성

• B-트리와 동일하게 균형을 유지하지만, 범위 검색에 더욱 효율적.

4. 레드-블랙 트리 (Red-Black Tree)

정의 및 구조

• 레드-블랙 트리는 노드에 색상(빨간색 또는 검은색)을 지정해 추가적인 균형 조건을 적용하는 이진 탐색 트리입니다.

균형 조건

• 모든 노드는 빨간색 또는 검은색.
• 루트와 리프(Null 노드)는 반드시 검은색.
• 빨간색 노드는 반드시 검은색 자식만.
• 한 노드에서 리프까지 가는 경로의 검은 노드 개수(Black-height)는 같음.

주요 연산

• 삽입/삭제: BST 방식에서 추가로 회전(Rotation)과 색상 변경으로 균형 유지.
• 회전(Rotation): 연산 후 트리 구조를 재조정하여 균형 조건 유지.
• 항상 O(log n) 복잡도 보장.

활용

• 자바의 TreeMap, HashMap(버킷 충돌 시)에서 많이 사용.

5. AVL 트리

• AVL 트리는 두 자식의 높이 차이가 최대 1인 자기 균형 이진 탐색 트리입니다.
• 레드-블랙 트리보다 더 엄격한 균형, 탐색 속도는 빠르나 삽입/삭제 시 회전 빈도가 많아 느릴 수 있습니다.

트리 비교 표

자바 백엔드 개발자를 위한 실무 조언

• 레드-블랙 트리는 TreeMap, TreeSet 등 메모리 기반 정렬 저장에 최적.
• B-트리, B+ 트리는 디스크 접근 효율을 위해 DB와 저장장치에서 많이 활용.
• BST는 구조가 단순하지만, 균형 유지가 어렵기 때문에 실무에선 직접 쓰이지 않음.

이러한 트리 구조를 잘 익히면, 검색, 정렬, 범위 질의 등 성능이 중요한 백엔드 로직을 효율적으로 구현할 수 있습니다.

references